package leetcode.Hot100;

import java.util.*;

/**
 * @author Cheng Jun
 * Description: 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
 * https://leetcode-cn.com/problems/top-k-frequent-elements/
 * @version 1.0
 * @date 2021/12/4 22:39
 * @see findKthLargest
 */
public class topKFrequent {

    public static void main(String[] args) {
        System.out.println(topKFrequent(new int[]{1, 1, 1, 2, 2, 3}, 2));
        System.out.println(topKFrequent1(new int[]{1, 1, 1, 2, 2, 3}, 2));
    }

    // 虽然时间复杂度，空间复杂度都很差，但也要自己写出来才能看题解
    @Deprecated
    public static int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> numMap = new HashMap<>();
        // 数组的数字出现次数进行统计
        for (int num : nums) {
            numMap.put(num, numMap.getOrDefault(num, 0) + 1);
        }
        // numMap 转换成 单调栈
        Deque<Integer> numStack = new ArrayDeque<>(numMap.size());
        for (Integer num : numMap.keySet()) {
            Integer numCounter = numMap.get(num);
            if (numStack.isEmpty()) {
                numStack.push(num);
            } else {
                int key = numStack.peek();
                Deque<Integer> tempStack = new ArrayDeque<>();
                while (numCounter < numMap.get(key)) {
                    tempStack.push(numStack.pop());
                    if (!numStack.isEmpty()) {
                        key = numStack.peek();
                    } else {
                        break;
                    }
                }
                numStack.push(num);
                while (!tempStack.isEmpty()) {
                    numStack.push(tempStack.pop());
                }
            }
        }
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = numStack.pop();
        }
        return ans;
    }

    public static int[] topKFrequent1(int[] nums, int k) {
        HashMap<Integer, Integer> numMap = new HashMap<>();
        // 数组的数字出现次数进行统计
        for (int num : nums) {
            numMap.put(num, numMap.getOrDefault(num, 0) + 1);
        }
        Queue<HashMap.Entry<Integer, Integer>> numQueue =
                new PriorityQueue<>((entry1, entry2) -> entry2.getValue() - entry1.getValue());
        numQueue.addAll(numMap.entrySet());
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = numQueue.poll().getKey();
        }
        return ans;
    }
}
